数据结构与算法 - 树(Day2)
子又生孙, 孙又生子, 子子孙孙无穷尽也.
树
一对多的层次关系的表示方法为树形结构.
树的定义:
树是由n(n>=0)各节点组成的有限集合.
若n=0, 则为空树.
若n>0, 则:
有一个特定的节点为根节点(root)
只有后继没有前驱
除根意外的其他节点都为树, 且互不相交.
每一个子树的根节点都有唯一前驱
树的概念:
- 节点的度(Degree): 节点的子树个数
- 树的度: 树的所有节点中最大的度数
- 叶节点(Leaf): 度=0的节点
- 父节点(Parent): 有子树的节点为其子树的根节点的父节点
- 子节点(Chld): A节点为B节点的父节点, B节点则为A的子节点
- 兄弟节点(Sibling): 具有同一个父节点的各节点彼此是兄弟节点
- 路径: 从节点n1到nk的路径为一个节点序列{n1,n2,…,nk}, ni为ni+1的父节点.
- 路径长度: 路径所包含边的个数为路径长度
- 祖先节点(Ancestor): 沿树根到某一节点路径上的所有节点都是该节点的祖先节点
- 子孙节点(Descendant): 某一节点的子树中的所有节点都是这个节点的子孙
- 节点层次(Level): 规定根节点在1层, 其他任意节点的整数是其父节点的层数+1
- 树的深度(Depth): 树中所有节点中的最大层次是该树的深度
- 有序树/无序树: 若结点的子树有次序排列，且先后次序不能互换，这样的树称为有序树，反之为无序树。
双亲表示法(顺序储存):
1
2
3
4
5
6
7
8
9
10
struct Ptnode{
TelemType data;
int parent; //双亲位置域
};
struct PTree{
Ptnode nodes[MAX_TREE_SIZE];
int n; //the number of nodes;
}- 优点: 便于涉及双亲的操作
- 缺点: 求节点的孩子时需要遍历整颗树
- 示意图:略
孩子表示法距离:
1
2
3
4
5
6
7
8
9
10
struct Ptnode{
TelemType data;
int child[m] //store the position of children
};
struct Ptree{
Ptnode nodes[MAX_TREE_SIZE];
int n; //the number of nodes
};- 优点: 便于涉及孩子的操作.
- 缺点: 采用的是同构的节点(节点中孩子空间个数取决于孩子最多的树的孩子个数, 造成不必要的浪费), 空间浪费. 求双亲不方便.
- 示意图: 略
孩子兄弟表示法:
1
2
3
4
5
6struct CSNode{
ELemType data;
int firstchild, nextsibling; //第一个孩子和右边的兄弟.
};
CSNode t[MAX_TREE_SIZE];- 优点: 节约空间
- 示意图: 略
二叉树
二叉树的基本概念:
- 度数=2的树, 每个节点最多有两个孩子
- 五种基本形态: (图略)
- 空二叉树
- 仅有根节点
- 右子树为空
- 左子树为空
- 左右子树都不为空
二叉树为有序树
二叉树性质:
- 二叉树的第i层最多有2^(i-1)个节点
- 深度为k的二叉树最多有2^(k)-1个节点
- 对任意一颗二叉树, 若其叶节点数为n0, 度为2的节点数为n2, 则一定满足n0=n2+1
- 具有n个节点的完全二叉树的深度为floor(log2(n))+1
- 对于一颗n个节点的完全二叉树, 对任意一个节点(编号为1), 有:
- 若i=1, 则节点i为根节点, 无父节点. 若i>1, 则其父节点的编号为i/2 (floor取整)
- 若2*i>n, 则节点i无左孩子(无子树),
满二叉树:
- 深度为k且有2^k - 1个节点的二叉树为完全二叉树
完全二叉树:
- 深度为k, 有n个节点的二叉树当且仅当其每个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时, 则为完全二叉树.
- 完全二叉树不一定为满二叉树, 满二叉树一定为完全二叉树
二叉树的存储结构:
数组顺序存储(完全二叉树)
顺序存储:
1
2
3
4
5
6
7struct node{
ElemType data;
int lchild;
int rchild;
};
node tree[MAX_TREE_SIZE];
int bt; //根节点位置二叉树的遍历:
先(根)序遍历: 先访问根
- 若二叉树为空, 则空操作. 否则:
- 访问根节点
- 先序遍历左子树
- 先序遍历右子树
1
2
3
4
5
6
7void proorder(int i){
if(!i)
return;
printf("%d ", v[i]);
proorder(l[i]);
proorder(r[i]);
}
- 若二叉树为空, 则空操作. 否则:
中(根)序遍历: 中间访问根
- 若二叉树为空, 则空操作, 否则:
- 中序遍历左子树
- 访问根节点
- 后序遍历右子树
1
2
3
4
5
6
7
8void inorder(int i){
if(!i)
return 0;
inorder(l[i]);
printf("%d ", v[i]);
//do something else;
inorder(r[i];)
}
- 若二叉树为空, 则空操作, 否则:
后(根)序遍历: 最后访问根
- 若二叉树为空, 则空操作, 否则:
- 后序遍历左子树
- 后序遍历右子树
- 访问根节点
1
2
3
4
5
6
7
8void sucorder(int i){
if(!i)
return 0;
sucorder(l[i]);
sucorder(r[i]);
printf("%d ", v[i]);
//do something else;
}- 若二叉树为空, 则空操作, 否则:
树的遍历
- 先根遍历
- 访问树的根节点
- 依次先根遍历每颗子树
- 后根遍历
- 依次后根遍历每颗子树
- 访问树的根节点
- 先根遍历
树和森林与二叉树的转化
- 树与二叉树的转化
- 在树中各元素(堂兄弟除外)之间加一根连线
- 对于任意节点保留与他第一个孩子的连线, 删除其他连线
- 将树整体顺时针旋转45°
- 树转化为二叉树根节点无右子树
- 森林与二叉树的转化
- 若F={T1,T2…Tm}是森林, 则
- 森林中的每颗树依次转化为二叉树, 并链接成上一个树的根的右子树.
- 树与二叉树的转化
二叉树的应用
二叉排序树(二叉查找树/二叉搜索树)为动态树表, 支持高效的查找和插入删除操作
- 该树或一颗空树, 或有如下特性的二叉树:
- 若根节点的左子树非空, 则左子树中所有节点的值均小于根节点值
- 若根节点的右子树非空, 则右子树中所有节点的值均大于根节点值
- 他的左右子树也分别为二叉排序树
- 高效方法: 转化为平衡二叉树
-
- 该树或一颗空树, 或有如下特性的二叉树:
最优二叉树(哈夫曼树/最优搜索树)
- 该树为带权路径长度最短的二叉树
- 每个叶节点带一个权值w, 且根到叶节点i的路径长度为L, 则树的带权路径长度为树中所有叶节点的权值与路径长度的乘积的总和
- 特性
- 当叶子上的权值均相同时, 完全二叉树一定是最优二叉树. 否则完全二叉树不一定是最优二叉树
- 在最优二叉树中, 权值越大的叶子离根越近
- 最优二叉树的形态不唯一, 但Wpl最小.
- 构造方法
- 找出最小的两个权值, 合并并作为左右子树, 根节点比较值为左右权值和
- 根节点视为叶节点参与第一步, 直到完全合并
哈夫曼编码
- 哈夫曼编码为哈夫曼树在电讯通讯中的应用之一
- 假定需要传送的电文是CDABB, 设A00,B01,C10,D11.
- 可翻译CDABB为1011000101
- 利用不等长编码将出现频率高的字母分配为短码, 频率低的字母分配为长码
- 要求短码不能为长码的前缀
- 生成这种编码的方法为哈夫曼树(右子树为1, 左子树为0, 叶子权值为出现频率, 到叶子的路径二进制和则为该字符的二进制编码)
并查集
- 树形的数据结构, 用于处理一些不相交集合(Disjoint Sets)的合并及查询问题. 常常在使用中以森林来表示.
- 初始化
- 把每个点所在集合初始化为其自身(时间复杂度O(n))
- 查找
- 查找元素所在的集合, 即根节点
- 合并
- 将两个元素所在的集合合并为一个集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20for(int i = 1;i<=n;i++)father[i] = i; //Init
int find(int x){ //找根
if(father[x] != x)
father[x] = find(father[x]); //路径压缩, 减少查询次数降低时间复杂度
return father[x];
}
void unionn(int x, int y){ //合并
x = find(x), y = find(y);
father[y] = x;
}
bool judge(int x, int y){ //判断是否是同集
x = find(x);
y = find(y);
if(x==y)
return true;
return false;
}
二叉树相关代码
1.输出叶节点
1
2
3
4
5
6
7
8void leaf(int i){
if(!i)
return ;
if(l[i]+r[i])
cout << i << endl;
leaf(l[i]);
leaf(r[i]);
}2. 计算树高度
1
2
3int Height(int i){
return i==0?0:max(Height(l[i]), Height(r[i])) + 1;
}3. 已知先序和中序求后序
1
2
3
4
5
6
7void build(int n, char *s1, char *s2, char *s){
if(n<=0) return;
int p = strchr(s2,s1[0]) - s2; //根节点在中序遍历中的位置
build(p, s1+1, s2, s); //L
build(n-p-1, s1+p+1, s2+p+1, s+p);
s[n-1] = s1[0];
}4. 插入数据 到二叉排序树
1
2
3
4
5
6
7
8
9
10
11
12void insert(int i, int x){
if(x<v[i])
if(l[i])
insert(l[i],x);
else
v[++p] = x, l[i] = p;
else
if(r[i])
insert(r[i],x);
else
v[++p] = x, r[i] = p;
}